Kebanyakan kisah hidup awal Theodora tidak diketahui; banyak yang diceritakan di dalam Sejarah Rahsia karya Prokopios yang kontroversial yang perlu diteliti untuk menentukan kebenarannya, terutamanya berkaitan sikap berat sebelah golongan bangsawan, masyarakat dan ahli sejarah Rom terhadap peranan wanita di luar batas adat masyarakat.[2]

Menurut Mikhael dari Syam, Theodora lahir di Mabbug, Syria;[3] Nikeforos Kallistos Xantopoulos menulis Theodora berasal dari Cyprus,[4] manakala Patria karya Georgios Kodinos mendakwa Theodora berasal dari Paflagonia. Theodora dilahirkan sekitar 500 TM.[5] Bapanya, Akakios, ialah seorang pelatih beruang untuk kumpulan Hijau di hipodrom Konstantaniah. Ibunya, yang namanya tidak direkod, seorang penari dan pelakon.[6] Ibu bapa Theodora mempunyai dua lagi anak perempuan, yang sulung bernama Komito dan yang bongsu Anastasia.[7] Selepas kematian bapanya, ibunya cepat-cepat berkahwin semula tetapi mereka tidak mempunyai sumber pendapatan: jawatan mendiang bapanya telah diberikan kepada seseorang yang telah menyogok penari balet utama, Asterios, yang juga memilih pekerja. Sewaktu Theodora berumur empat tahun, ibunya membawa anak-anaknya memakai kalungan ke hipodrom untuk meminta bantuan kumpulan Hijau, tetapi mereka mengabaikan dia. Oleh itu, ibu Theodora pergi kepada kumpulan Biru.[8] Kumpulan Biru mengasihani mereka dan memberikan bapa tiri Theodora bekerja sebagai penjaga beruang—menyelamatkan mereka daripada kemiskinan.

Menurut Sejarah Rahsia karya Prokopios, Theodora mengikuti contoh kakaknya Komito sejak kecil dan bekerja di dalam rumah pelacuran di Konstantaniah, melayan pelanggan berstatus rendah dan tinggi; kemudiannya, dia membuat persembahan di atas pentas. Dalam catatan terkenal Edward Gibbon tentang Theodora, yang berdasarkan Sejarah Rahsia, beliau menulis:

Dia menawarkan pesona jualan dirinya kepada pelbagai golongan yang berbeza, orang keramaian dan asing dari pelbagai lapisan masyarakat dan pangkat. Kekasih beruntung yang dijanjikan malam bersamanya sering kali dihalau oleh seseorang yang lebih kuat atau lebih kaya. Orang ramai akan mengelak daripada bertemu dengannya ketika dia berjalan di luar bagi mengelakkan terlibat dalam skandal atau godaan.[9]

Theodora, menurut catatan Prokopios, menjadi terkenal kerana persembahan lucahnya dalam Leda dan Sang Angsa.[10][11] Pekerjaan berlakon pada zaman itu sering melibatkan persembahan tidak senonoh di atas pentas dan perkhidmatan seks di luar pentas. Sama ada tepat atau tidak kelakuan Theodora ini adalah sangsi kerana pelakon-pelakon wanita pada era itu sering dikatakan membuat perbuatan stereotaip sedemikian. Sesetengah ahli sejarah berpendapat bahawa golongan yang berkuasa pada masa itu mungkin mereka kisah-kisah buruk ini apabila Theodora menjadi permaisuri kerana takut dia akan mempengaruhi empayar. Melihat Theodora ditunjukkan secara negatif akan merendahkan ancaman dia terhadap mereka dan status quo.[12] Penerangan terperinci dan lucah mengenai kehidupan silam Theodora di dalam "Sejarah Rahsia" dilihat fitnah menurut beberapa tafsiran moden; beberapa penulis kontemporari, seperti Ioannes dari Efesus, jelas menggambarkan Theodora berasal "dari rumah pelacuran". Selaras dengan prinsip-prinsip mengenai taubat dan pengampunan dalam agama Kristian, Ioannes melihat penebusan diri Theodora sebagai cerita positif.[13] Strategi wanita menggunakan badannya untuk keuntungan politik bukanlah sesuatu yang baharu, dan wanita yang melakukannya dianggap mempunyai kuasa pengaruh yang sama seperti lelaki, dan pandang sama oleh ahli sejarah kontemporari zaman Rom dan Byzantium. Hal ini juga boleh disamakan dengan ahli sejarah Rom, Takitus, dan karangannya mengenai Maharani Messalina. Takitus memandang hina terhadap Messalina, sama seperti Prokopios memandang hina Theodora dengan cerita seks bebasnya, yang menurutnya tidak mencerminkan kebangsawanan orang berkuasa. Di dalam istana, Maharani Theodora ada dua peranan: menjadi maharani dan menjadi isteri maharaja. Dia telah memainkan dua peranan dan pengaruhnya di belakang takhta telah menimbulkan banyak perasaan kurang senang dengan ahli-ahli sejarah mengenai wanita berkuasa.[14] Pada masa ini, Theodora mungkin telah bertemu dengan bakal isteri Belisarius, Antonina, yang kemudiannya akan menyertai para wanita istana, diketuai oleh Theodora.

Kemudian, Theodora pergi ke Afrika Utara sebagai gundik kepada seorang pegawai Syam bernama Hekebolus semasa beliau pergi ke Pentapolis Libya untuk menjadi gabenor.[15] Selepas dilayan dengan teruk dan ditinggalkan oleh Hekebolus, dia memulakan perjalanan pulang ke ibu kota Empayar Rom, Konstantaniah, lalu singgah di Iskandariah, Mesir.Ada yang menspekulasikan bahawa dia bertemu dengan Paus Timotius III di Iskandariah, paus mazhab Miafisitisme, dan mungkin waktu itu jugalah dia memeluk agama Kristian Miafisitisme. Dari Iskandariah dia pergi ke Antokiah, di mana dia bertemu dengan seorang penari kumpulan Biru bernama Makedonia. Ada kemungkinan bahawa Makedonia ialah ampamar kepada Justinianus.

Sewaktu Justinianus ingin mengahwini Theodora, beliau dihalang oleh satu undang-undang Rom dari zaman Konstantianos yang melarang senator daripada mengahwini pelakon. Pada tahun 524, maharaja Iostinos I menggubal undang-undang baharu untuk membenarkan bekas-bekas pelakon yang telah berubah berkahwin dengan orang di luar pangkat mereka secara sah jika diizinkan oleh maharaja.[16] Undang-undang tersebut juga menyatakan bahawa anak perempuan pelakon wanita akan bebas untuk mengahwini lelaki daripada mana-mana pangkat. Ini akan membenarkan anak perempuan luar nikah kepada Theodora (yang namanya hilang dalam sejarah) untuk berkahwin dengan salah seorang kaum kerabat Anastasius, maharaja yang terdahulu. Beberapa sumber mendakwa bahawa dia juga mempunyai seorang anak lelaki luar nikah yang bernama Ioannes.[17] Prokopios pernah menulis tentang Ioannes yang datang ke Konstantaniah sebagai seorang pemuda. Ioannes mendakwa bahawa ayahnya telah mengaku ketika nazak bahawa Ioannes ialah anak luar nikah kepada Theodora. Ayah Ioannes berkata beliau membawanya pergi kerana Theodora pasti akan membunuhnya jika ayah beliau tidak lari dan merahsiakan perkara itu. Menurut penceritaan Prokopios, apabila Theodora dapat tahu tentang kedatangan dan apa yang dikatanya itu, Theodora menghantar beliau ke satu tempat yang tidak diketahui secara senyap dan khabar mereka tidak didengari oleh sesiapa sesudah itu. Akan tetapi, menurut seorang sarjana pengajian klasik, James Allan Evans, beliau percaya dakwaan ini tidak benar kerana Theodora pernah mengakui anak perempuan luar nikahnya.[18] Tak lama selepas undang-undang Iostinos diluluskan, Justinianus berkahwin dengan Theodora.[17]